package lcr;

import java.util.HashMap;
import java.util.Map;

public class Test0050 {
}

class Solution0050_1 {
    Map<Long, Integer> map = new HashMap<>();
    int ans = 0;

    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L,1);
        dfs(root,0,targetSum);
        return ans;
    }

    public void dfs(TreeNode root, long sum, int target) {
        if (root==null) return;
        sum += root.val;
        ans+=map.getOrDefault(sum-target,0);

        map.put(sum,map.getOrDefault(sum,0)+1);
        dfs(root.left,sum,target);
        dfs(root.right,sum,target);
        map.put(sum,map.get(sum)-1);
    }
}